package org.byteDance.l092;

/**
 * @Author yu
 * @Date 2022/3/6
 */
public class Solution {

    public static void main(String[] args) {

        ListNode listNode = new ListNode(5);
        ListNode listNode1 = new ListNode(4, listNode);
        ListNode listNode2 = new ListNode(3, listNode1);
        ListNode listNode3 = new ListNode(2, listNode2);
        ListNode listNode4 = new ListNode(1, listNode3);

        Solution solution = new Solution();
        ListNode res = solution.reverseBetween4(listNode4, 2, 4);

        while (res != null) {
            System.out.println(res.val);
            res = res.next;
        }

    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null || left == right) {
            return head;
        }

        ListNode listNode = new ListNode(0, head), temp = null, next = null, firstNode = null, lastNode = null, res = listNode;
        //int count = 0;
        int count = left;

        // firstNode 记录反转链表后的 链表前一个节点 例：1-2-3-4-5 中的 1，用于以后区间链表反转后拼接反转链表的头节点 1-4-3-2-5
        // lastNode 记录反转链表后的 链表最后一个节点 例：1-2-3-4-5 中的 2，用于以后区间链表反转后拼接后面没有被反转的节点 1-4-3-2-5
        while (left-- > 0) {
            firstNode = res;
            res = res.next;
            lastNode = res;
        }

        // 反转链表
        while (res != null && right-- >= count) {
            next = res.next;
            res.next = temp;
            temp = res;
            res = next;
        }

        // 拼接头节点
        if (firstNode != null) {
            firstNode.next = temp;
        }

        // 拼接尾节点
        if (lastNode != null) {
            lastNode.next = next;
        }

        return listNode.next;
    }

    public ListNode reverseBetween2(ListNode head, int left, int right) {
        ListNode node = new ListNode(0, head), temp = null, firstNode = null, lastNode = null, res = node, next = null;
        int count = left;

        while (left-- > 0) {
            firstNode = res;
            res = res.next;
            lastNode = res;
        }

        // 反转链表
        while (res.next != null && right-- >= count) {
            next = res.next;
            res.next = temp;
            temp = res;
            res = next;
        }

        if (firstNode != null) {
            firstNode.next = temp;
        }

        if (next != null) {
            lastNode.next = next;
        }

        return node.next;
    }

    public ListNode reverseBetween3(ListNode head, int left, int right) {
        ListNode temp = new ListNode();
        temp.next = head;
        ListNode start = null, end = null, cur = null, next = null, pre = null, node = temp;
        int count = left;

        while (left-- > 0) {
            start = node;
            node = node.next;
            end = node;
        }

        cur = end;
        while (cur != null && right-- >= count) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        if (start != null) {
            start.next = pre;
        }
        if (cur != null) {
            end.next = cur;
        }
        return temp.next;
    }

    // 1 2 3 4 5
    public ListNode reverseBetween4(ListNode head, int left, int right) {
        ListNode temp = new ListNode();
        temp.next = head;
        ListNode res = temp, start = null, end = null, pre = null, node = null, cur = null;
        int count = left;
        while (left-- > 0) {
            start = res;
            res = res.next;
            end = res;
        }

        cur = res;
        while (cur != null && right-- >= count) {
            node = cur.next;
            cur.next = pre;
            pre = cur;
            cur = node;
        }

        if (start != null) {
            start.next = pre;
        }
        if (end != null) {
            end.next = cur;
        }

        return temp.next;
    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}